home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
HPAVC
/
HPAVC CD-ROM.iso
/
FRCOMP.ZIP
/
fracpack.c
next >
Wrap
C/C++ Source or Header
|
1992-11-12
|
13KB
|
327 lines
Here is some C source for fractal image compression.
Notes:
1) You will need DJGPP (a C compiler for DOS ) to handle the arrays.
2) It is available for anonymous ftp at
ftp.math.niu.edu:/pub/msdos/djgpp.stuff/v109 (i think, look around)
3) A 386+387 or higher is REALLY required.
4) This should compile on other systems... graphics stuff will need to
change though...
5) Images are 256x256x256 shades of gray. Totals 65536 bytes. 1 byte/pixel
6) I'm not a C programmer, so don't complain about the code or lack of
documentation.
7) Get the paper /pub/inls-ucsd/fractal-2.0.tar from lyapunov.ucsd.edu
It is a very good description of the process by yuval fisher.
8) Decompression code will be sent in another message.
9) Enjoy... there is also some later work of mine in /pub/young-fractal
at the same anonymous ftp site.
10) It will be updated soon... (2+ weeks)
----------------- Cut Here -------------------
/*****************************************************************************
FRACPACK - a program for
FRACTAL IMAGE COMPRESSION
image.krd ==> image.ifs
*****************************************************************************/
#include <stdio.h>
#include <stdlib.h>
#include <graphics.h>
#include <math.h>
int main(int argc, char **argv)
{
unsigned char IMAGE [256][256], Range[8][8][8], Domain[8][8];
int REDGE[32][32], DEDGE[241][241];
FILE *in, *out;
char *inf, *outf, rmsstr[13];
int xsize=256, ysize=256, x, y, dx, dy, rx, ry, bestdx, bestdy, inrx, inry;
int class1, class2, class3, class4, i, besti, nflips=8, rsize, rsize2,
plotdx, plotdy, usegraph;
long int suma, sumb, sumab, suma2, sumb2, sumx, sumx2;
long int DSUMS[241][241][2];
float fsuma, fsumb, fsumab, fsuma2, fsumb2, fmagica;
float bests, besto, scale, offset, rms, bestrms, ifs_tolerance;
struct trans_t {
unsigned char dx;
unsigned char dy;
signed char scale;
short int offset : 13;
unsigned short int flip : 3;
} trans[1];
if (argc < 4)
{
printf("usage: fracpack rms infile.ext outfile.ext [graphics flag]");
return 1;
}
ifs_tolerance = atof(argv[1]);
inf = argv[2]; outf = argv[3];
if (argc == 5) usegraph = -1;
else usegraph = 0;
if ((in = fopen(inf, "rb")) == NULL)
{
fprintf(stderr, "Cannot open input file.\n");
return 1;
}
if ((out = fopen(outf, "wb")) == NULL)
{
fprintf(stderr, "Cannot open output file.\n");
return 1;
}
fclose(out);
printf("Compressing %s to %s with an rms of
%4.2f\n",inf,outf,ifs_tolerance);
ifs_tolerance=ifs_tolerance*ifs_tolerance;
if (usegraph)
{
GrSetMode(GR_default_graphics);
for (x = 0; x < xsize; x++)
GrSetColor(x,x,x,x);
}
/* Get .KRD bitmap 8-bit-grey-scale pixels, put in IMAGE array. */
for (y = 0; y < ysize; y++)
for (x = 0; x < xsize; x++)
{
IMAGE[y][x] = fgetc(in);
if (usegraph)
{
GrPlot(x,y,IMAGE[y][x]);
GrPlot(x+300,y,IMAGE[y][x]);
}
}
fclose(in);
/*************************************************************************/
/* Classify Range's */
/*************************************************************************/
if (!usegraph) printf("Classifying RangeS\n");
for (ry = 0; ry < ysize; ry+=8)
for (rx = 0; rx < xsize; rx+=8)
{
for (y = 0; y < 8; y++)
for (x = 0; x < 8; x++)
Range[0][y][x] = IMAGE [ ry +y ] [ rx +x ];
class1 = (Range[0][0][0]==Range[0][0][1]) +
(Range[0][0][1]==Range[0][0][2])
+ (Range[0][0][2]==Range[0][0][3]) +
(Range[0][0][3]==Range[0][0][4])
+ (Range[0][0][4]==Range[0][0][5]) +
(Range[0][0][5]==Range[0][0][6])
+ (Range[0][0][6]==Range[0][0][7]);
class2 = (Range[0][7][0]==Range[0][7][1]) +
(Range[0][7][1]==Range[0][7][2])
+ (Range[0][7][2]==Range[0][7][3]) +
(Range[0][7][3]==Range[0][7][4])
+ (Range[0][7][4]==Range[0][7][5]) +
(Range[0][7][5]==Range[0][7][6])
+ (Range[0][7][6]==Range[0][7][7]);
class3 = (Range[0][0][0]==Range[0][1][0]) +
(Range[0][1][0]==Range[0][2][0])
+ (Range[0][2][0]==Range[0][3][0]) +
(Range[0][3][0]==Range[0][4][0])
+ (Range[0][4][0]==Range[0][5][0]) +
(Range[0][5][0]==Range[0][6][0])
+ (Range[0][6][0]==Range[0][7][0]);
class4 = (Range[0][0][7]==Range[0][1][7]) +
(Range[0][1][7]==Range[0][2][7])
+ (Range[0][2][7]==Range[0][3][7]) +
(Range[0][3][7]==Range[0][4][7])
+ (Range[0][4][7]==Range[0][5][7]) +
(Range[0][5][7]==Range[0][6][7])
+ (Range[0][6][7]==Range[0][7][7]);
class1 = class1*1000 + class2*100 + class3*10 + class4;
REDGE[ry>>3][rx>>3] = class1;
}
/*************************************************************************/
/* Classify Domain's and compute DSUMS array */
/*************************************************************************/
if (!usegraph) printf("Classifying DomainS\n");
for (dy = 0; dy < ysize - 15; dy++)
for (dx = 0; dx < xsize - 15; dx++)
{
DSUMS[dy][dx][0] = DSUMS[dy][dx][1] = 0;
if (usegraph) GrPlot(dx+308,dy+8,384);
for (y = 0; y < 16; y+=2)
for (x = 0; x < 16; x+=2)
{
Domain[y>>1][x>>1] = (IMAGE[dy+y ][dx+x ]
+ IMAGE[dy+y ][dx+x+1]
+ IMAGE[dy+y+1][dx+x ]
+ IMAGE[dy+y+1][dx+x+1]) >> 2;
DSUMS[dy][dx][0] += Domain[y>>1][x>>1];
DSUMS[dy][dx][1] += Domain[y>>1][x>>1]*Domain[y>>1][x>>1];
}
class1 = (Domain[0][0]==Domain[0][1]) + (Domain[0][1]==Domain[0][2])
+ (Domain[0][2]==Domain[0][3]) + (Domain[0][3]==Domain[0][4])
+ (Domain[0][4]==Domain[0][5]) + (Domain[0][5]==Domain[0][6])
+ (Domain[0][6]==Domain[0][7]);
class2 = (Domain[7][0]==Domain[7][1]) + (Domain[7][1]==Domain[7][2])
+ (Domain[7][2]==Domain[7][3]) + (Domain[7][3]==Domain[7][4])
+ (Domain[7][4]==Domain[7][5]) + (Domain[7][5]==Domain[7][6])
+ (Domain[7][6]==Domain[7][7]);
class3 = (Domain[0][0]==Domain[1][0]) + (Domain[1][0]==Domain[2][0])
+ (Domain[2][0]==Domain[3][0]) + (Domain[3][0]==Domain[4][0])
+ (Domain[4][0]==Domain[5][0]) + (Domain[5][0]==Domain[6][0])
+ (Domain[6][0]==Domain[7][0]);
class4 = (Domain[0][7]==Domain[1][7]) + (Domain[1][7]==Domain[2][7])
+ (Domain[2][7]==Domain[3][7]) + (Domain[3][7]==Domain[4][7])
+ (Domain[4][7]==Domain[5][7]) + (Domain[5][7]==Domain[6][7])
+ (Domain[6][7]==Domain[7][7]);
class1 = class1*1000 + class2*100 + class3*10 + class4;
DEDGE[dy][dx] = class1;
if (usegraph) GrPlot(dx+308,dy+8,384);
}
/* Run through all non-overlapping 8x8 "R" blocks in the image */
for (ry = 0; ry < ysize; ry+=8)
for (rx = 0; rx < xsize; rx+=8)
{
if (usegraph)
{
GrLine(rx ,ry ,rx ,ry+7,384);
GrLine(rx ,ry ,rx+7,ry ,384);
GrLine(rx+7,ry ,rx+7,ry+7,384);
GrLine(rx ,ry+7,rx+7,ry+7,384);
}
else printf("Entering Range Loop\n");
sumb = sumb2 = 0;
/*************************************************************************/
/* Grab Range (and its "flips"). */
/*************************************************************************/
for (y = 0; y < 8; y++)
for (x = 0; x < 8; x++)
{
Range[0][y][x] = IMAGE [ ry +y ] [ rx +x ];
Range[1][y][x] = IMAGE [ ry+7-x ] [ rx +y ];
Range[2][y][x] = IMAGE [ ry+7-y ] [ rx+7-x ];
Range[3][y][x] = IMAGE [ ry +x ] [ rx+7-y ];
Range[4][y][x] = IMAGE [ ry+7-y ] [ rx +x ];
Range[5][y][x] = IMAGE [ ry+7-x ] [ rx+7-y ];
Range[6][y][x] = IMAGE [ ry +y ] [ rx+7-x ];
Range[7][y][x] = IMAGE [ ry +x ] [ rx +y ];
sumb+=Range[0][y][x]; sumb2+=Range[0][y][x]*Range[0][y][x];
}
/*************************************************************************/
/* Grab Domain, compare with Range(s) */
/*************************************************************************/
bestrms = 10000000000.;
for (dy = 0; dy < ysize - 15; dy++)
for (dx = 0; dx < xsize - 15; dx++)
if ((DEDGE[dy][dx] == REDGE[ry>>3][rx>>3])||
(((dx - 16 < rx)&&(rx < dx + 16))&&
((dy - 16 < ry)&&(ry < dy + 16))))
{
if (usegraph)
{
plotdy = dy; plotdx = dx;
GrPlot(dx+308,dy+8,384);
}
for (y = 0; y < 16; y+=2)
for (x = 0; x < 16; x+=2)
Domain[y>>1][x>>1] = (IMAGE[dy+y ][dx+x ]
+ IMAGE[dy+y ][dx+x+1]
+ IMAGE[dy+y+1][dx+x ]
+ IMAGE[dy+y+1][dx+x+1]) >> 2;
suma = DSUMS[dy][dx][0]; suma2 = DSUMS[dy][dx][1];
fsuma=suma; fsuma2=suma2;
fsumb=sumb; fsumb2=sumb2;
fmagica = (float) (suma2 - suma*suma/64.);
for (i = 0; i < nflips; i++)
{
sumab = 0;
for (y = 0; y < 8; y++)
for (x = 0; x < 8; x++)
sumab += Domain[y][x] * Range[i][y][x];
fsumab = sumab;
if (fmagica != 0.)
scale = (fsumab - fsuma*fsumb/64.)/fmagica;
else scale = 0;
if (scale*scale < 1.44)
{
scale = (signed char) 127. * scale / 1.2;
scale = 1.2 * scale / 127.;
offset = (short int) (fsumb - scale*fsuma)/64.;
rms = (fsumb2 + scale*(scale*fsuma2 - 2*fsumab +
2*offset*fsuma)
+ offset*(offset*64. - 2.*fsumb)) / 64.;
if (rms > 10000) (i = nflips);
if (rms < bestrms)
{
if (!usegraph) printf("%3i%4i%4i%4i%4i%2i
%12.8f\n",REDGE[ry][rx],dx, dy, rx, ry, i, rms);
besti = i; bestrms = rms; bestdx = dx; bestdy =
dy;
bests = scale; besto = offset;
}
if (rms < ifs_tolerance) goto gotbest;
}
}
} /* End of Domain LOOP */
gotbest:
if (usegraph)
{
for (dy = 0; dy <= plotdy; dy++)
for (dx = 0; (dx <= plotdx) || ((dy < plotdy)&&(dx < xsize - 15));
dx++)
if ((DEDGE[dy][dx] == REDGE[ry>>3][rx>>3])||
(((dx - 16 < rx)&&(rx < dx + 16))&&
((dy - 16 < ry)&&(ry < dy + 16))))
GrPlot(dx+308,dy+8,384);
sprintf(rmsstr,"%8.4f",sqrt((double)bestrms));
GrTextXY(560,20,rmsstr,255,0);
}
if ((out = fopen(outf, "ab")) == NULL)
{
fprintf(stderr, "Cannot open output file.\n");
return 1;
}
if (!usegraph)
{
printf("best rms=%12.8f,dx=%5i,dy=%5i,flip=%i for
rx=%5i,ry=%5i,s=%12.5f\n", bestrms,
bestdx, bestdy, besti, rx, ry,bests);
}
trans[0].dx = bestdx;
trans[0].dy = bestdy;
trans[0].flip = besti;
trans[0].scale = 127. * bests / 1.2;
trans[0].offset = besto;
fwrite(trans, sizeof(struct trans_t), 1, out); /* write out compressed
file */
fclose(out);
if (usegraph)
{
GrLine(rx ,ry ,rx ,ry+7,384);
GrLine(rx ,ry ,rx+7,ry ,384);
GrLine(rx+7,ry ,rx+7,ry+7,384);
GrLine(rx ,ry+7,rx+7,ry+7,384);
}
}
if (usegraph) GrSetMode(GR_default_text);
/* All done. Whew... */
return 0;
}